#include <iostream>
#include <cstdlib>

#ifndef __hhxxttxs_DIC__
#define __hhxxttxs_DIC__

template <typename DTYPE>
class Node
{
private:
    DTYPE data;
    Node* next;
    Node* prev;
public:
    Node();
    Node(DTYPE _val);
    ~Node(){};
    DTYPE get_data() const;
    void set_data(DTYPE _val);
    Node* get_next() const;
    Node* get_prev() const;
    void set_next(Node* _add);
    void set_prev(Node* _add);
};
//Node 函数实现
template<typename DTYPE>
Node<DTYPE>::Node()
{
    next = NULL;
    prev = NULL;
};
template<typename DTYPE>
Node<DTYPE>::Node(DTYPE _val)
{
    data = _val;
    next = NULL;
    prev = NULL;
};
template<typename DTYPE>
DTYPE Node<DTYPE>::get_data() const
{
    return data;
};
template<typename DTYPE>
void Node<DTYPE>::set_data(DTYPE _val)
{
    data = _val;
};
template<typename DTYPE>
Node<DTYPE>* Node<DTYPE>::get_next() const
{
    return next;
};
template<typename DTYPE>
Node<DTYPE>* Node<DTYPE>::get_prev() const
{
    return prev;
};
template<typename DTYPE>
void Node<DTYPE>::set_next(Node<DTYPE>* _add)
{
    next = _add;
};
template<typename DTYPE>
void Node<DTYPE>::set_prev(Node<DTYPE>* _add)
{
    prev = _add;
};


template <typename DTYPE>
class LL{
    Node<DTYPE>* head;
    Node<DTYPE>* tail;
    public:
    LL();
    ~LL();
    void append(DTYPE _val);
    Node<DTYPE>* get_tail() const;
    Node<DTYPE>* get_head() const;
    void del(Node<DTYPE>* _add);
    void sort();
};
//链表函数实现
template <typename DTYPE>
LL<DTYPE>::LL(){
    head=NULL;
    tail=NULL;
};
template <typename DTYPE>
LL<DTYPE>::~LL(){
    if(head!=NULL){
        Node<DTYPE>* p = head;
        while(p->get_next()!=NULL){
            Node<DTYPE> *t=p;
            p=p->get_next();
            delete t;
        }
        delete p;
    }
};
template <typename DTYPE>
void LL<DTYPE>::append(DTYPE _val){
    Node<DTYPE>* p=new Node<DTYPE>;
    p->set_data(_val);
    p->set_prev(tail);
    if (head == tail)
        if(head==NULL)
        head = p;
        else
        head->set_next(p);
    else
        tail->set_next(p);
    tail=p;
};
template <typename DTYPE>
Node<DTYPE>* LL<DTYPE>::get_head() const{
    return head;
};
template <typename DTYPE>
Node<DTYPE>* LL<DTYPE>::get_tail() const{
    return tail;
};
template <typename DTYPE>
void LL<DTYPE>::del(Node<DTYPE>* _add){
    if(_add->get_next()!=NULL)
    _add->get_next()->set_prev(_add->get_prev());
    if(_add->get_prev()!=NULL)
    _add->get_prev()->set_next(_add->get_next());
    delete _add;
};
template <typename DTYPE>
void LL<DTYPE>::sort(){};

template <typename DTYPE>
class STACK{
    private:
    LL<DTYPE> arr;
    int top;
    public:
    STACK(){
        top=0;
    };
    STACK(DTYPE _val){
        arr.append(_val);
        top=1;
    };
    ~STACK(){};
    bool EMPTY() const{
        if(top==0)
        return true;
        else
        return false;
    };
    void PUSH(DTYPE _val){
        arr.append(_val);
        top=top+1;
    };
    DTYPE POP{
        if(EMPTY())
        return -1;
        DTYPE a=arr.get_tail()->get_data();
        top=top-1;
        del(arr.get_tail());
        return a;
    };
};

class QUEUE{
    public:
    bool
    int ENQUEUE(QUEUE _q, DTYPE _x){}
    int DEQUEUE(QUEUE _q){}
};//*/

#else
//Do nothing.
#endif